{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Hills and Valleys in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countHillValley"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计数组中峰和谷的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。如果两侧距 <code>i</code> 最近的不相等邻居的值均小于 <code>nums[i]</code> ，则下标 <code>i</code> 是 <code>nums</code> 中，某个峰的一部分。类似地，如果两侧距 <code>i</code> 最近的不相等邻居的值均大于 <code>nums[i]</code> ，则下标 <code>i</code> 是 <code>nums</code> 中某个谷的一部分。对于相邻下标&nbsp;<code>i</code> 和 <code>j</code> ，如果&nbsp;<code>nums[i] == nums[j]</code> ， 则认为这两下标属于 <strong>同一个</strong> 峰或谷。</p>\n",
    "\n",
    "<p>注意，要使某个下标所做峰或谷的一部分，那么它左右两侧必须 <strong>都</strong> 存在不相等邻居。</p>\n",
    "\n",
    "<p>返回 <code>nums</code> 中峰和谷的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4,1,1,6,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "在下标 0 ：由于 2 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。\n",
    "在下标 1 ：4 的最近不相等邻居是 2 和 1 。由于 4 &gt; 2 且 4 &gt; 1 ，下标 1 是一个峰。\n",
    "在下标 2 ：1 的最近不相等邻居是 4 和 6 。由于 1 &lt; 4 且 1 &lt; 6 ，下标 2 是一个谷。\n",
    "在下标 3 ：1 的最近不相等邻居是 4 和 6 。由于 1 &lt; 4 且 1 &lt; 6 ，下标 3 符合谷的定义，但需要注意它和下标 2 是同一个谷的一部分。\n",
    "在下标 4 ：6 的最近不相等邻居是 1 和 5 。由于 6 &gt; 1 且 6 &gt; 5 ，下标 4 是一个峰。\n",
    "在下标 5 ：由于 5 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。\n",
    "共有 3 个峰和谷，所以返回 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [6,6,5,5,4,1]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "在下标 0 ：由于 6 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。\n",
    "在下标 1 ：由于 6 的左侧不存在不相等邻居，所以下标 1 既不是峰也不是谷。\n",
    "在下标 2 ：5 的最近不相等邻居是 6 和 4 。由于 5 &lt; 6 且 5 &gt; 4 ，下标 2 既不是峰也不是谷。\n",
    "在下标 3 ：5 的最近不相等邻居是 6 和 4 。由于 5 &lt; 6 且 5 &gt; 4 ，下标 3 既不是峰也不是谷。\n",
    "在下标 4 ：4 的最近不相等邻居是 5 和 1 。由于 4 &lt; 5 且 4 &gt; 1 ，下标 4 既不是峰也不是谷。\n",
    "在下标 5 ：由于 1 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。\n",
    "共有 0 个峰和谷，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-hills-and-valleys-in-an-array](https://leetcode.cn/problems/count-hills-and-valleys-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-hills-and-valleys-in-an-array](https://leetcode.cn/problems/count-hills-and-valleys-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,1,1,6,5]', '[6,6,5,5,4,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countHillValley(self, nums):\n",
    "        flag, tmp, ans = 0, nums[0], 0\n",
    "        for x in nums[1:]:\n",
    "            if   x > tmp:\n",
    "                if flag == -1: ans += 1\n",
    "                flag = 1\n",
    "            elif x < tmp:\n",
    "                if flag ==  1: ans += 1\n",
    "                flag = - 1\n",
    "            tmp = x\n",
    "        return ans                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cur = nums[0]\n",
    "        num = 0\n",
    "        ans = []\n",
    "        for i in nums:\n",
    "            if i == cur:\n",
    "                num += 1\n",
    "                if num <= 1:\n",
    "                    ans.append(i)\n",
    "            else :\n",
    "                cur = i\n",
    "                num = 1\n",
    "                ans.append(i)\n",
    "        res = 0\n",
    "        for i in range(1, len(ans)-1):\n",
    "            if ans[i] > ans[i-1] and ans[i] > ans[i+1]:\n",
    "                res += 1\n",
    "            if ans[i] < ans[i-1] and ans[i] < ans[i+1]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        nlen = len(nums)\n",
    "        i,j = 0,1\n",
    "        res = 0\n",
    "        while i < j and j < nlen -1:\n",
    "            if nums[i] < nums[j] and nums[j] > nums[j+1]:\n",
    "                # 满足峰\n",
    "                res += 1\n",
    "                i = j\n",
    "            elif nums[i] == nums[j]:\n",
    "                i = j\n",
    "            elif nums[j] < nums[i] and nums[j] < nums[j+1]:\n",
    "                # 满足谷\n",
    "                res += 1\n",
    "                i = j\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        s = list()\n",
    "        for num in nums:\n",
    "            if not s or num != s[-1]:\n",
    "                s.append(num)\n",
    "        n = len(s)\n",
    "        #print(s)\n",
    "        ans = 0\n",
    "        for i in range(1,n-1):\n",
    "            if s[i] > s[i-1] and s[i] > s[i+1]:\n",
    "                ans +=1\n",
    "            if s[i] < s[i-1] and s[i] < s[i+1]:\n",
    "                ans +=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        cur = 0\n",
    "        start = nums[0]\n",
    "        n = len(nums)\n",
    "        #找到第一个差别\n",
    "        while nums[cur] == start:\n",
    "            cur += 1\n",
    "            if cur == n:\n",
    "                return 0\n",
    "        # 当前是否为上坡\n",
    "        up = nums[cur] > nums[cur - 1]\n",
    "        ans = 0\n",
    "        for i in range(cur+1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                if (nums[i] > nums[i-1]) ^ up:\n",
    "                    ans += 1\n",
    "                    up = not up\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        cur = 1\n",
    "        n = len(nums)\n",
    "        #找到第一个差别\n",
    "        while nums[cur] == nums[0]:\n",
    "            cur += 1\n",
    "            if cur == n:\n",
    "                return 0\n",
    "        # 当前是否为上坡\n",
    "        up = nums[cur] > nums[cur - 1]\n",
    "        ans = 0\n",
    "        for i in range(cur+1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                if (nums[i] > nums[i-1]) ^ up:\n",
    "                    ans += 1\n",
    "                    up = not up\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0 or i == len(nums) - 1:\n",
    "                continue\n",
    "            elif nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            else:\n",
    "                templ, tempr = i, i\n",
    "                curr = nums[i]\n",
    "                while nums[templ] == curr and templ > 0:\n",
    "                    templ -= 1\n",
    "\n",
    "                while nums[tempr] == curr and tempr < len(nums) - 1:\n",
    "                    tempr += 1\n",
    "                \n",
    "                if templ < 0 or tempr > len(nums) -1:\n",
    "                    continue\n",
    "                \n",
    "                if nums[templ] < curr and curr > nums[tempr]:\n",
    "                    res += 1\n",
    "\n",
    "                if nums[templ] > curr and curr < nums[tempr]:\n",
    "                    res += 1\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        cur = 0\n",
    "        start = nums[0]\n",
    "        n = len(nums)\n",
    "        #找到第一个差别\n",
    "        while nums[cur] == start:\n",
    "            cur += 1\n",
    "            if cur == n:\n",
    "                return 0\n",
    "        # 当前是否为上坡\n",
    "        up = nums[cur] > nums[cur - 1]\n",
    "        ans = 0\n",
    "        for i in range(cur+1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                if (nums[i] > nums[i-1]) ^ up:\n",
    "                    ans += 1\n",
    "                    up = not up\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        i,j=0,1\n",
    "        while j<len(nums):\n",
    "            if nums[i]<nums[j-1] and nums[j-1]>nums[j]:\n",
    "                ans+=1\n",
    "                i=j-1\n",
    "            elif nums[i]>nums[j-1] and nums[j-1]<nums[j]:\n",
    "                ans+=1\n",
    "                i=j-1\n",
    "            else:\n",
    "                j+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        left=nums[0]\n",
    "        flag=0\n",
    "        i=0\n",
    "        stack=[]\n",
    "        while i<len(nums)-1:\n",
    "            if i==0 or nums[i]==left:\n",
    "                i+=1\n",
    "                continue\n",
    "            if flag==0:\n",
    "                if nums[i]<left:\n",
    "                    flag=-1  # 表示谷\n",
    "\n",
    "                else:\n",
    "                    flag=1 # 表示峰\n",
    "            \n",
    "            if flag==-1:\n",
    "                if nums[i]<nums[i+1]:\n",
    "                    res+=1\n",
    "                    flag=1\n",
    "                    left=nums[i]\n",
    "                    stack.append(i)\n",
    "            else:\n",
    "                if nums[i]>nums[i+1]:\n",
    "                    print(i)\n",
    "                    res+=1\n",
    "                    flag=-1\n",
    "                    left=nums[i]\n",
    "                    stack.append(i)\n",
    "            i+=1\n",
    "        print(stack)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "                    \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countHillValley(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         p = 1\n",
    "#         ans = 0\n",
    "#         while p < n - 1:\n",
    "#             l = r = p\n",
    "#             while l >= 0 and nums[l] == nums[p]:\n",
    "#                 l -= 1\n",
    "#             while r < n and nums[r] == nums[p]:\n",
    "#                 r += 1\n",
    "#             if l < 0 or r > n - 1:\n",
    "#                 p += 1\n",
    "#                 continue\n",
    "#             if nums[l] < nums[p] and nums[r] < nums[p]:\n",
    "#                 ans += 1\n",
    "#             if nums[l] > nums[p] and nums[r] > nums[p]:\n",
    "#                 ans += 1\n",
    "#             p = r\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:   \n",
    "        count = 0\n",
    "        i = 1\n",
    "        while i < len(nums) - 1:\n",
    "            if nums[i] == nums[i - 1]:\n",
    "                i += 1\n",
    "                continue\n",
    "            j = i + 1\n",
    "            while nums[j] == nums[i]:\n",
    "                j += 1\n",
    "                if j >= len(nums):\n",
    "                    return count\n",
    "            \n",
    "            if (nums[i] > nums[i - 1] and nums[i] > nums[j]) or (nums[i] < nums[i - 1] and nums[i] < nums[j]):\n",
    "                count += 1\n",
    "            \n",
    "            i = j\n",
    "        return count\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        index=[]\n",
    "        res=0\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i]==nums[i+1]:\n",
    "                index.append(i)          \n",
    "        new_nums=[num for i ,num in enumerate(nums) if i not in index]\n",
    "        for j in range(1,len(new_nums)-1):\n",
    "            if (new_nums[j]>new_nums[j-1] and new_nums[j]>new_nums[j+1]) or (new_nums[j]<new_nums[j-1] and new_nums[j]<new_nums[j+1]):\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countHillValley(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         p = 1\n",
    "#         ans = 0\n",
    "#         while p < n - 1:\n",
    "#             l = r = p\n",
    "#             while l >= 0 and nums[l] == nums[p]:\n",
    "#                 l -= 1\n",
    "#             while r < n and nums[r] == nums[p]:\n",
    "#                 r += 1\n",
    "#             if l < 0 or r > n - 1:\n",
    "#                 p += 1\n",
    "#                 continue\n",
    "#             if nums[l] < nums[p] and nums[r] < nums[p]:\n",
    "#                 ans += 1\n",
    "#             if nums[l] > nums[p] and nums[r] > nums[p]:\n",
    "#                 ans += 1\n",
    "#             p = r\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            v = nums[i]\n",
    "\n",
    "            # 往后找到第一个不等于v的数\n",
    "            while i < n and nums[i] == v: i += 1\n",
    "            # 使用一个条件判断峰/谷\n",
    "            if start > 0 and i < n and ((nums[start-1] < v)  == (nums[i] < v)):\n",
    "                res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        num = 0\n",
    "        cur = nums[0]\n",
    "        for i in nums:\n",
    "            if i == cur:\n",
    "                cur = i\n",
    "                num += 1\n",
    "                if num == 1:\n",
    "                    ans.append(i)\n",
    "            else:\n",
    "                cur = i\n",
    "                num = 1\n",
    "                ans.append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, len(ans)-1):\n",
    "            if ans[i] > ans[i-1] and ans[i] > ans[i+1]:\n",
    "                res += 1\n",
    "            if ans[i] < ans[i-1] and ans[i] < ans[i+1]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        #我们希望数组中每个数不重复,可以预处理实现\n",
    "        arr=[nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]==nums[i-1]: continue\n",
    "            arr.append(nums[i])\n",
    "        ans=0\n",
    "        #枚举中间下标\n",
    "        for i in range(1,len(arr)-1):\n",
    "            if (arr[i]>arr[i-1] and arr[i]>arr[i+1]) or (arr[i]<arr[i-1] and arr[i]<arr[i+1]):\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        new=[nums[i] for i in range(len(nums)) if i==0 or nums[i]!=nums[i-1]]\n",
    "        count=0\n",
    "        for i in range(1,len(new)-1):\n",
    "            if new[i-1]<new[i]>new[i+1] or new[i-1]>new[i]<new[i+1]:\n",
    "                count+=1\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countHillValley(self, nums):\n",
    "        flag, tmp, ans = 0, nums[0], 0\n",
    "        for x in nums[1:]:\n",
    "            if   x > tmp:\n",
    "                if flag == -1: ans += 1\n",
    "                flag = 1\n",
    "            elif x < tmp:\n",
    "                if flag ==  1: ans += 1\n",
    "                flag = - 1\n",
    "            tmp = x\n",
    "        return ans                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "         for i in range(len(nums)-1,0,-1):\n",
    "             if nums[i]==nums[i-1]:\n",
    "                 nums.pop(i)\n",
    "         count=0\n",
    "         for i in range(len(nums)):\n",
    "            if i-1>=0 and i+1<len(nums) and nums[i]>nums[i-1] and nums[i]>nums[i+1]:\n",
    "                count+=1\n",
    "            elif i-1>=0 and i+1<len(nums) and (nums[i]<nums[i-1] and nums[i]<nums[i+1]):\n",
    "                count+=1\n",
    "         return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        hill = 0\n",
    "        valley = 0\n",
    "\n",
    "        for i in range(1, len(nums) - 1):\n",
    "            \n",
    "            if nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "\n",
    "            left = i - 1\n",
    "            right = i + 1\n",
    "\n",
    "            while (left > 0 and nums[left] == nums[i]):\n",
    "                left -= 1\n",
    "\n",
    "            while (right < len(nums) - 1 and nums[right] == nums[i]):\n",
    "                right += 1\n",
    "\n",
    "            if nums[i] > nums[left] and nums[i] > nums[right]:\n",
    "                hill += 1\n",
    "\n",
    "            if nums[i] < nums[left] and nums[i] < nums[right]:\n",
    "                valley += 1\n",
    "\n",
    "        return hill + valley\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        last_state = -1 \n",
    "        res = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                if last_state == 1:\n",
    "                    res += 1\n",
    "                last_state = 0\n",
    "            elif nums[i]<nums[i-1]:\n",
    "                if last_state == 0:\n",
    "                    res +=1 \n",
    "                last_state = 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1,n-1):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            left = 0\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if nums[j]>nums[i]:\n",
    "                    left = 1\n",
    "                    break\n",
    "                elif nums[j]<nums[i]:\n",
    "                    left = -1\n",
    "                    break\n",
    "            right = 0\n",
    "            for j in range(i+1,n):\n",
    "                if nums[j]>nums[i]:\n",
    "                    right=1\n",
    "                    break\n",
    "                elif nums[j]<nums[i]:\n",
    "                    right=-1\n",
    "                    break\n",
    "            if left==right and left!=0:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        c, ans = 0, 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                if c == -1:\n",
    "                    ans += 1\n",
    "                c = 1\n",
    "            elif nums[i] < nums[i - 1]:\n",
    "                if c == 1:\n",
    "                    ans += 1\n",
    "                c = - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n1,n2 = nums[0],nums[1]\n",
    "        ans = 0\n",
    "        for i in nums[2:]:\n",
    "            if n2 > n1 and n2 > i or n2 < n1 and n2 < i:\n",
    "                ans += 1\n",
    "            if n2 != i:\n",
    "                n1,n2 = n2,i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        pre = nums[0]\n",
    "        for i in range(1,n-1):\n",
    "            L,R = -1,-1\n",
    "            v = nums[i]\n",
    "            if v == pre:continue\n",
    "            pre = v\n",
    "            for l in range(i-1,-1,-1):\n",
    "                if nums[l] != v:L = nums[l];break\n",
    "            for r in range(i+1,n):\n",
    "                if nums[r] != v:R = nums[r];break\n",
    "            if L == -1 or R == -1:continue\n",
    "            if (L > v and R > v) or (L < v and R < v):res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        count=0\n",
    "        sta=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                if sta==1:\n",
    "                    count+=1\n",
    "                sta=-1 \n",
    "            elif nums[i]>nums[i-1]:\n",
    "                if sta==-1:\n",
    "                    count+=1\n",
    "                sta=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            l = inf\n",
    "            for k in range(i - 1, -1, -1):\n",
    "                if nums[k] != nums[i]:\n",
    "                    l = nums[k]\n",
    "                    break\n",
    "            r = inf\n",
    "            for k in range(i + 1, n):\n",
    "                if nums[k] != nums[i]:\n",
    "                    r = nums[k]\n",
    "                    break\n",
    "            \n",
    "            if l == inf or r == inf: continue\n",
    "            if l < nums[i] and nums[i] > r:\n",
    "                ans += 1\n",
    "            if l > nums[i] and r > nums[i]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = 1\n",
    "        ans = 0\n",
    "        while p < n - 1:\n",
    "            l = r = p\n",
    "            while l >= 0 and nums[l] == nums[p]:\n",
    "                l -= 1\n",
    "            while r < n and nums[r] == nums[p]:\n",
    "                r += 1\n",
    "            if l < 0 or r > n - 1:\n",
    "                p += 1\n",
    "                continue\n",
    "            if nums[l] < nums[p] and nums[r] < nums[p]:\n",
    "                ans += 1\n",
    "            if nums[l] > nums[p] and nums[r] > nums[p]:\n",
    "                ans += 1\n",
    "            p = r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        flag = 0    # 1表示大，-1表示小\n",
    "        temp = nums[0]\n",
    "        count = 0   # 保存个数\n",
    "        for x in nums[1:]:\n",
    "            if x > temp:\n",
    "                if flag == -1: count += 1\n",
    "                flag = 1\n",
    "            elif x < temp:\n",
    "                if flag == 1: count += 1\n",
    "                flag = -1\n",
    "            temp = x    \n",
    "        return count    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        flag = 0    # 1表示大，-1表示小\n",
    "        temp = nums[0]\n",
    "        count = 0   # 保存个数\n",
    "        for x in nums[1:]:\n",
    "            if x > temp:\n",
    "                if flag == -1: count += 1\n",
    "                flag = 1\n",
    "            elif x < temp:\n",
    "                if flag == 1: count += 1\n",
    "                flag = -1\n",
    "            temp = x    \n",
    "        return count    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        flag = 0\n",
    "        cnt = 0\n",
    "        for i in range(1,l-1):\n",
    "            if nums[i]<nums[i-1] and nums[i]<nums[i+1]:\n",
    "                cnt += 1\n",
    "            elif nums[i]>nums[i-1] and nums[i]>nums[i+1]:\n",
    "                cnt += 1\n",
    "            elif nums[i]<nums[i-1] and nums[i]==nums[i+1]:\n",
    "                flag = -1\n",
    "            elif nums[i]>nums[i-1] and nums[i]==nums[i+1]:\n",
    "                flag = 1\n",
    "            elif nums[i]==nums[i-1] and nums[i]<nums[i+1]:\n",
    "                if flag ==-1:\n",
    "                    cnt+=1\n",
    "            elif nums[i]==nums[i-1] and nums[i]>nums[i+1]:\n",
    "                if flag ==1:\n",
    "                    cnt+=1\n",
    "        return cnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        ##除去首尾，遍历每个i与隔壁相同跳过\n",
    "        for i in range(1,n-1):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                continue \n",
    "            l=0\n",
    "            ### 确认左边的最近不等邻居状态\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if nums[j]>nums[i]:\n",
    "                    l=1\n",
    "                    break\n",
    "                elif nums[j]<nums[i]:\n",
    "                    l=-1\n",
    "                    break\n",
    "            ### 确认右边的最近不等邻居状态\n",
    "            r=0\n",
    "            for j in range(i+1,n):\n",
    "                if nums[j]>nums[i]:\n",
    "                    r=1\n",
    "                    break\n",
    "                elif nums[j]<nums[i]:\n",
    "                    r=-1\n",
    "                    break\n",
    "            if l==r and l!=0:\n",
    "                ans+=1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        # 如果是递增状态，设flag=1，递减状态设flag=-1，相等的时候无变化，如果遍历到的当前状态与上一个状态不一样则说明是峰或谷\n",
    "        flag, last, cnt = 0, nums[0], 0\n",
    "        for x in nums[1:]:\n",
    "            if x > last:\n",
    "                if flag == -1:\n",
    "                    cnt += 1\n",
    "                flag = 1\n",
    "            if x < last:\n",
    "                if flag == 1:\n",
    "                    cnt += 1\n",
    "                flag = -1\n",
    "            last = x\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        a, b = nums[0], nums[1]\n",
    "        峰和谷的数量 = 0\n",
    "        for i in nums[2:]:\n",
    "            if b > i:\n",
    "                if a < b:\n",
    "                    峰和谷的数量 += 1\n",
    "                a, b = b, i\n",
    "            elif b < i:\n",
    "                if a > b:\n",
    "                    峰和谷的数量 += 1\n",
    "                a, b = b, i\n",
    "        return 峰和谷的数量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        res = 0   # 峰与谷的数量\n",
    "        n = len(nums)\n",
    "        for i in range(1, n - 1):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                # 去重\n",
    "                continue\n",
    "            left = 0   # 左边可能的不相等邻居对应状态\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if nums[j] > nums[i]:\n",
    "                    left = 1\n",
    "                    break\n",
    "                elif nums[j] < nums[i]:\n",
    "                    left = -1\n",
    "                    break\n",
    "            right = 0   # 右边可能的不相等邻居对应状态\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] > nums[i]:\n",
    "                    right = 1\n",
    "                    break\n",
    "                elif nums[j] < nums[i]:\n",
    "                    right = -1\n",
    "                    break\n",
    "            if left == right and left != 0:\n",
    "                # 此时下标 i 为峰或谷的一部分\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n1,n2 = nums[0],nums[1]\n",
    "        ans = 0\n",
    "        for i in nums[2:]:\n",
    "            if n2 > n1 and n2 > i or n2 < n1 and n2 < i:\n",
    "                ans += 1\n",
    "            if n2 != i:\n",
    "                n1,n2 = n2,i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        #我们希望数组中每个数不重复,因为这样就很好做了,可以预处理实现\n",
    "        arr=[nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]==nums[i-1]: continue\n",
    "            arr.append(nums[i])\n",
    "        ans=0\n",
    "        #枚举中间下标\n",
    "        for i in range(1,len(arr)-1):\n",
    "            if (arr[i]>arr[i-1] and arr[i]>arr[i+1]) or (arr[i]<arr[i-1] and arr[i]<arr[i+1]):\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        flag,tmp,ans = 0,nums[0],0\n",
    "        for x in nums[1:]:\n",
    "            if x>tmp:\n",
    "                if flag==-1:ans += 1\n",
    "                flag = 1\n",
    "            elif x<tmp:\n",
    "                if flag==1:ans += 1\n",
    "                flag = -1\n",
    "            tmp = x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        left=nums[0]\n",
    "        flag=0\n",
    "        i=0\n",
    "        while i<len(nums)-1:\n",
    "            if i==0 or nums[i]==left:\n",
    "                i+=1\n",
    "                continue\n",
    "            if flag==0:\n",
    "                if nums[i]<left:\n",
    "                    flag=-1  # 表示谷\n",
    "\n",
    "                else:\n",
    "                    flag=1 # 表示峰\n",
    "            \n",
    "            if flag==-1:\n",
    "                if nums[i]<nums[i+1]:\n",
    "                    res+=1\n",
    "                    flag=1\n",
    "                    left=nums[i]\n",
    "            else:\n",
    "                if nums[i]>nums[i+1]:\n",
    "                    res+=1\n",
    "                    flag=-1\n",
    "                    left=nums[i]\n",
    "            i+=1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "                    \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        q=[]\n",
    "        for n in nums:\n",
    "            if not q or n!=q[-1]:\n",
    "                q.append(n)\n",
    "        n=len(q)\n",
    "        ans=0\n",
    "        for i in range(1,n-1):\n",
    "            if (q[i]>q[i-1] and q[i]>q[i+1]) or (q[i]<q[i-1] and q[i]<q[i+1]):\n",
    "                ans+=1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=[]\n",
    "        # set会改变原本的顺序\n",
    "        ans.append(nums[0])\n",
    "        print(set(nums))\n",
    "        for i in range(1,n):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                pass\n",
    "            else:\n",
    "                ans.append(nums[i])\n",
    "        print(ans)\n",
    "        m=len(ans)\n",
    "        res=0\n",
    "        for i in range(1,m-1):\n",
    "            if ans[i-1]<ans[i] and ans[i]>ans[i+1]:\n",
    "                res+=1\n",
    "            if ans[i-1]>ans[i] and ans[i]<ans[i+1]:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for x in range(1,n - 1):\n",
    "            if nums[x] == nums[x-1]:\n",
    "                continue\n",
    "            left = 0\n",
    "            for i in range(x - 1,-1,-1):\n",
    "                if nums[i] > nums[x]:\n",
    "                    left = 1\n",
    "                    break\n",
    "                elif nums[i] < nums[x]:\n",
    "                    left = -1\n",
    "                    break\n",
    "            right = 0\n",
    "            for j in range(x + 1,n):\n",
    "                if nums[j] > nums[x]:\n",
    "                    right = 1\n",
    "                    break\n",
    "                elif nums[j] < nums[x]:\n",
    "                    right = -1\n",
    "                    break\n",
    "            if left == right and left != 0:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            start = i \n",
    "            x = nums[i]\n",
    "            while i < n and nums[i] == x:\n",
    "                i += 1\n",
    "            if start > 0 and i < n and (nums[start -  1] > x) == (nums[i] > x):\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        count=0\n",
    "        last=0\n",
    "        list1=[]\n",
    "        list2=[]\n",
    "        for i in range(1,len(nums)-1):\n",
    "            r=''\n",
    "            l=''\n",
    "            for x in range(i+1,len(nums)):\n",
    "                if nums[x]>nums[i]:\n",
    "                    r='g' #1 gu\n",
    "                    break\n",
    "                elif nums[x]<nums[i]:\n",
    "                    r='f' #2 ding\n",
    "                    break\n",
    "            for y in range(i,-1,-1):\n",
    "                if nums[y]>nums[i]:\n",
    "                    l='g'\n",
    "                    break\n",
    "                elif nums[y]<nums[i]:\n",
    "                    l='f'\n",
    "                    break \n",
    "            if r=='g' and l=='g' and last!='g':\n",
    "                count+=1\n",
    "                last='g'\n",
    "                list1.append(i)\n",
    "            elif r=='f' and l=='f' and last!='f':\n",
    "                count+=1\n",
    "                last='f'\n",
    "                list2.append(i)\n",
    "        return count\n",
    "        #return list1,list2\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        i=0\n",
    "        left=nums[0]\n",
    "        while i<len(nums):\n",
    "            if i==len(nums)-1:\n",
    "                break\n",
    "            if left==nums[i]:\n",
    "                i+=1\n",
    "                continue\n",
    "            else:\n",
    "                j=i+1\n",
    "                while j<len(nums):\n",
    "                    if nums[j]==nums[i]:\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        break\n",
    "                if j<len(nums):\n",
    "                    right=nums[j]\n",
    "                    if (left<nums[i] and right<nums[i]) or (left>nums[i] and right>nums[i]):\n",
    "                        res+=1\n",
    "                left=nums[i]\n",
    "                i=j\n",
    "        return res\n",
    "                \n",
    "\n",
    "            \n",
    "                    \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        flag,tmp,ans = 0,nums[0],0\n",
    "        for x in nums[1:]:\n",
    "            if x>tmp:\n",
    "                if flag==-1:ans += 1\n",
    "                flag = 1\n",
    "            elif x<tmp:\n",
    "                if flag==1:ans += 1\n",
    "                flag = -1\n",
    "            tmp = x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=[]\n",
    "        # set会改变原本的顺序\n",
    "        ans.append(nums[0])\n",
    "        # 去重，要保留原本的顺序，不能用 set\n",
    "        for i in range(1,n):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                pass\n",
    "            else:\n",
    "                ans.append(nums[i])\n",
    "        print(ans)\n",
    "        m=len(ans)\n",
    "        res=0\n",
    "        for i in range(1,m-1):\n",
    "            if ans[i-1]<ans[i] and ans[i]>ans[i+1]:\n",
    "                res+=1\n",
    "            if ans[i-1]>ans[i] and ans[i]<ans[i+1]:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 1\n",
    "        ans = 0\n",
    "        while i < n - 1:\n",
    "            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:\n",
    "                ans += 1\n",
    "            elif nums[i] < nums[i - 1] and nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            elif nums[i] > nums[i - 1] and nums[i] == nums[i + 1]:\n",
    "                while i < n - 1 and nums[i] == nums[i + 1]:\n",
    "                    i += 1\n",
    "                if i < n - 1 and nums[i] > nums[i + 1]:\n",
    "                    ans += 1\n",
    "            elif nums[i] < nums[i - 1] and nums[i] == nums[i + 1]:\n",
    "                while i < n - 1 and nums[i] == nums[i + 1]:\n",
    "                    i += 1\n",
    "                if i < n - 1 and nums[i] < nums[i + 1]:\n",
    "                    ans += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        zipNums = []\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0 or n != nums[i - 1]:\n",
    "                zipNums.append(n)\n",
    "        r = 0\n",
    "        for i, n in enumerate(zipNums):\n",
    "            if 0 < i < len(zipNums)-1:\n",
    "                if zipNums[i - 1] < n and zipNums[i + 1] < n:\n",
    "                    r += 1\n",
    "                if zipNums[i - 1] > n and zipNums[i + 1] > n:\n",
    "                    r += 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        cur = 0\n",
    "        start = nums[0]\n",
    "        n = len(nums)\n",
    "        #找到第一个差别\n",
    "        while nums[cur] == start:\n",
    "            cur += 1\n",
    "            if cur == n:\n",
    "                return 0\n",
    "        # 当前是否为上坡\n",
    "        up = nums[cur] > nums[cur - 1]\n",
    "        ans = 0\n",
    "        for i in range(cur+1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                if (nums[i] > nums[i-1]) ^ up:\n",
    "                    ans += 1\n",
    "                    up = not up\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        ret,n=0,len(nums)\n",
    "        for i in range(1,n-1):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            left,right=i-1,i+1\n",
    "            while left>0 and nums[left]==nums[i]:\n",
    "                left-=1\n",
    "            while right<n-1 and nums[right]==nums[i]:\n",
    "                right+=1\n",
    "            if nums[i]>nums[left] and nums[i]>nums[right]:\n",
    "                ret+=1\n",
    "            elif nums[i]<nums[left] and nums[i]<nums[right]:\n",
    "                ret+=1\n",
    "        return ret\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        flag = 0    # 1表示大，-1表示小\n",
    "        temp = nums[0]\n",
    "        count = 0   # 保存个数\n",
    "        for x in nums[1:]:\n",
    "            if x > temp:\n",
    "                if flag == -1: count += 1\n",
    "                flag = 1\n",
    "            elif x < temp:\n",
    "                if flag == 1: count += 1\n",
    "                flag = -1\n",
    "            temp = x    \n",
    "        return count    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        tag = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if(nums[i-1]>nums[i]):\n",
    "                if(tag ==1): ans+=1\n",
    "                tag = 2\n",
    "            if(nums[i-1]< nums[i]):\n",
    "                if(tag == 2): ans+=1\n",
    "                tag =1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = nums[0]\n",
    "        for i in range(1, len(nums)-1):\n",
    "            cur = nums[i]\n",
    "            suc = nums[i+1]\n",
    "            if cur != suc:\n",
    "                if (pre-cur) * (suc-cur) > 0:\n",
    "                    ans += 1\n",
    "                pre = cur\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        ans = [nums[0]]\n",
    "        ret = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                ans.append(nums[i])\n",
    "        for i in range(1, len(ans) - 1):\n",
    "            if ans[i - 1] < ans[i] and ans[i] > ans[i + 1]:\n",
    "                ret += 1\n",
    "            if ans[i - 1] > ans[i] and ans[i] < ans[i + 1]:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countHillValley(self, nums: List[int]) -> int:\n",
    "#         ans=0\n",
    "#         n=len(nums)\n",
    "#         ##除去首尾，遍历每个i与隔壁相同跳过\n",
    "#         for i in range(1,n-1):\n",
    "#             if nums[i]==nums[i-1]:\n",
    "#                 continue \n",
    "#             l=0\n",
    "#             ### 确认左边的最近不等邻居状态\n",
    "#             for j in range(i-1,-1,-1):\n",
    "#                 if nums[j]>nums[i]:\n",
    "#                     l=1\n",
    "#                     break\n",
    "#                 elif nums[j]<nums[i]:\n",
    "#                     l=-1\n",
    "#                     break\n",
    "#             ### 确认右边的最近不等邻居状态\n",
    "#             r=0\n",
    "#             for j in range(i+1,n):\n",
    "#                 if nums[j]>nums[i]:\n",
    "#                     r=1\n",
    "#                     break\n",
    "#                 elif nums[j]<nums[i]:\n",
    "#                     r=-1\n",
    "#                     break\n",
    "#             if l==r and l!=0:\n",
    "#                 ans+=1\n",
    "            \n",
    "#         return ans\n",
    "\n",
    "### 官码（逐个判断）\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        res = 0   # 峰与谷的数量\n",
    "        n = len(nums)\n",
    "        for i in range(1, n - 1):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                # 去重\n",
    "                continue\n",
    "            left = 0   # 左边可能的不相等邻居对应状态\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if nums[j] > nums[i]:\n",
    "                    left = 1\n",
    "                    break\n",
    "                elif nums[j] < nums[i]:\n",
    "                    left = -1\n",
    "                    break\n",
    "            right = 0   # 右边可能的不相等邻居对应状态\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] > nums[i]:\n",
    "                    right = 1\n",
    "                    break\n",
    "                elif nums[j] < nums[i]:\n",
    "                    right = -1\n",
    "                    break\n",
    "            if left == right and left != 0:\n",
    "                # 此时下标 i 为峰或谷的一部分\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if i+1 < len(nums) and nums[i]==nums[i+1]:\n",
    "                continue\n",
    "            if i+1 < len(nums) and ((nums[i] <pre and nums[i]<nums[i+1]) or (nums[i] >pre and nums[i]>nums[i+1])):\n",
    "                ans += 1\n",
    "            pre = nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        lst = []\n",
    "        for num in nums:\n",
    "            if lst and lst[-1] == num:\n",
    "                continue\n",
    "            lst.append(num)\n",
    "        ans = 0\n",
    "        m = len(lst)\n",
    "        for i in range(1, m-1):\n",
    "            a, b, c = lst[i-1:i+2]\n",
    "            if b<a and b < c:\n",
    "                ans += 1\n",
    "            elif b>a and b > c:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countHillValley(self, nums: List[int]) -> int:\r\n",
    "        count = 0\r\n",
    "        i = 1\r\n",
    "        n = len(nums)\r\n",
    "        if n < 3:\r\n",
    "            return count\r\n",
    "        while i < n - 1:\r\n",
    "            j = i + 1\r\n",
    "            while j < n - 1 and nums[i] == nums[j]:\r\n",
    "                j += 1\r\n",
    "            before_i, i = i, j\r\n",
    "            if (nums[before_i - 1] > nums[before_i] and nums[j] > nums[before_i]) or (nums[before_i - 1] < nums[before_i] and nums[j] < nums[before_i]):\r\n",
    "                count += 1\r\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countHillValley(self, nums: List[int]) -> int:\n",
    "        # 查找当前索引i左侧第一个与nums[i]不同的数字的索引，如果不存在返回-1\n",
    "        def findLeftDiff(i: int) -> int:\n",
    "            while i > 0 and nums[i] == nums[i-1]:\n",
    "                i -= 1\n",
    "            return i-1 if i > 0 else -1\n",
    "        \n",
    "        # 查找当前索引i右侧第一个与nums[i]不同的数字的索引，如果不存在返回len(nums)\n",
    "        def findRightDiff(i: int) -> int:\n",
    "            while i < len(nums) - 1 and nums[i] == nums[i+1]:\n",
    "                i += 1\n",
    "            return i+1 if i < len(nums) - 1 else len(nums)\n",
    "        \n",
    "        count = 0\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        while i < n:\n",
    "            left = findLeftDiff(i)\n",
    "            right = findRightDiff(i)\n",
    "            \n",
    "            # 如果存在左右两边的不相等邻居\n",
    "            if left >= 0 and right < n:\n",
    "                # 判断是否为峰\n",
    "                if nums[i] > nums[left] and nums[i] > nums[right]:\n",
    "                    count += 1\n",
    "                    i = right  # 跳过这个峰的所有部分\n",
    "                    continue\n",
    "                # 判断是否为谷\n",
    "                elif nums[i] < nums[left] and nums[i] < nums[right]:\n",
    "                    count += 1\n",
    "                    i = right  # 跳过这个谷的所有部分\n",
    "                    continue\n",
    "            i += 1\n",
    "        return count\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
